// 将一个整数拆分成若干个数之和，求若干数之积的最大值
/*
第一个数从2开始，以后每个数可以被拆成两个或多个数。
确定dp数组内容：dp[i] 表示i拆分后的最大积
那么dp[i] 可以是i拆分成两个数或两个以上数，使用j=1直到i来遍历
两个数：(i-j)*j    多个数dp[i-j]*j  ,dp[i-j]就是i-j拆分后的最大积
也会出现两种拆法都不如前面的j，所以要保留目前的最大值
*/
#include <vector>
#include <algorithm>
using std::vector;
using std::max;
int integerBreak(int n)
{
    vector<int> dp(n + 1);
    dp[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
            dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
    }
    return dp[n];
}